class Solution {
public:
    vector<int> father,size,rank;
    int find(int x){
        return x == father[x] ? x : find(father[x]);
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        
        if(rank[x] < rank[y]){
            swap(x,y);
        }
        
        size[x] += size[y];
        father[y] = x;
        if(rank[x] == rank[y]) rank[x] += 1;
    }
    int getSize(int x){
        int fx = find(x);
        return size[fx];
    }
    
    int dir[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
    
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int m = grid.size();
        int n = grid[0].size();
        int l = hits.size();
        vector<int> ret(l);
        
        father.resize(m*n+1);
        size.resize(m*n+1,1);
        rank.resize(m*n+1,1);
        
        for(int i = 0;i < m * n + 1;i++){
            father[i] = i;
        }
        
        vector<vector<int> > copy(grid);
        for(auto& vc : hits){
            copy[vc[0]][vc[1]] = 0;
        }
        
        for(int i = 0;i < n;i++){
            if(copy[0][i] == 0) continue;
            Union(m*n,i);
        }
        
        for(int i = 1;i < m;i++){
            for(int j = 0;j < n;j++){
                if(copy[i][j] == 0) continue;
                if(copy[i-1][j] == 1){
                    Union((i-1)*n+j,i*n+j);
                }
                if(j > 0 && copy[i][j-1] == 1){
                    Union(i*n+j-1,i*n+j);
                }
            }
        }
        
        for(int k = l - 1;k >= 0;k--){
            int i = hits[k][0];
            int j = hits[k][1];
            if(grid[i][j] == 0) continue;
            
            int oldS = getSize(m*n);
            
            if(i == 0){
                Union(j,m*n);
            }
            
            for(int p = 0;p < 4;p++){
                int x = i + dir[p][0];
                int y = j + dir[p][1];
                if(x >= 0 && x < m && y >= 0 && y < n && copy[x][y] == 1){
                    Union(i*n+j,x*n+y);
                }
            }
            
            int newS = getSize(m*n);
            ret[k] = max(0,newS - oldS - 1);
            copy[i][j] = 1;
            
        }
        return ret;
    }
};
